package com.lwx.leetcode.dp;

/**
 * 打家劫舍
 */
public class Top198 {
    public static void main(String[] args) {
        Top198 o = new Top198();
        int[] nums = {1,1};
        int rob = o.rob(nums);
        System.out.println(rob);
    }
    //如果按照奇数偶数分组，那么2,1,1,2这种情况不能计算正确
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        //以nums[i]为结尾的最大值
        int[] dp = new int[nums.length];
        int maxEle = 0;
        dp[0] = nums[0];
        dp[1] = nums[1];
        //处理只有两个元素的情况
        maxEle = dp[0]> dp[1] ? dp[0]: dp[1];

        for (int i = 2; i < nums.length; i++) {
            for (int j = 0; j <= i-2 ; j++) {
                dp[i] = Math.max(dp[i], dp[j]+ nums[i]);
                if(dp[i] > maxEle){
                    maxEle = dp[i];
                }
            }
        }
        return maxEle;
    }
}
